package dp;

public class P516 {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        if (len <= 1) {
            return len;
        }
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        for (int col = 1; col < len; col++) {
            for (int row = 0; row < len - col; row++) {
                int left = row;
                int right = row + col;
                char lc = s.charAt(left);
                char rc = s.charAt(right);
                if (lc == rc) {
                    dp[left][right] = left + 1 <= right - 1 ? dp[left + 1][right - 1] + 2 : 2;
                } else {//不相等
                    dp[left][right] = Math.max(dp[left + 1][right], dp[left][right - 1]);
                }
            }
        }
        return dp[0][len-1];
    }

    public static void main(String[] args) {
        int i = new P516().longestPalindromeSubseq("cbbd");
        System.out.println(i);
    }
}
